#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
#define max 1000
typedef struct Binode
{
    char data;
    struct Binode *lchild, *rchild;
}BiNode,*Bitree;

void levmid(Bitree &T, char kid, int kidmid, string mid, int l);

void cinpremid(string &pre,string &mid)
{
    cout << "请输入先序遍历序列:";
    cin >> pre;
    cout << "请输入中序遍历序列:";
    cin >> mid;
}

void cinlevmid(string &lev,string &mid)
{
    cout << "请输入层次遍历序列:";
    cin >> lev;
    cout << "请输入中序遍历序列:";
    cin >> mid;
}

Bitree premidCreatTree(string pre, int prebegin, int preend, string mid, int midbegin, int midend) 
{//先序+中序建立二叉树
    Bitree T;
    if(preend-prebegin+1==0)//子树先序序列为空，先序序列与中序序列长度相同
    {
        T = NULL;
        return T;
    }
    int midroot = 0, i;//midroot为中序序列中根的位置
    for(i = midbegin; i <= midend; i++)
    {
        if(mid[i] == pre[prebegin])//先序序列的第一个点为根结点
        {
            midroot = i;//中序序列中根结点的位置
            break;
        }
    }
    T = new BiNode;
    T->data = pre[prebegin];//先序序列的第一个结点为根
    T->lchild = premidCreatTree(pre, prebegin + 1, prebegin + (midroot - midbegin), mid, midbegin, midroot - 1);
    //(prebegin + 1)~(prebegin + (midroot - midbegin))为左子树先序序列
    //(midbegin)~( midroot - 1)为左子树中序序列
    T->rchild = premidCreatTree(pre, preend - (midend - midroot) + 1, preend, mid, midroot + 1, midend);
    return T;
}
/*
Bitree levmidCreatTree(string mid, string lev, int midbegin, int midend) 
{
    Bitree T;
    string llv, rlv;
    if(midend-midbegin+1<=0)
    {
        T = NULL;
        return T;
    }
    int midroot = 0, i; // midroot为中序序列中根的位置
    for(i = midbegin; i <= midend; i++)
    {
        if(mid[i] == lev[0])//层次序列的第一个点为根结点
        {
            midroot = i;//中序序列中根结点的位置
            break;
        }
    }
    T = new BiNode;
    T->data = lev[0];//层次序列的第一个结点为根
    llv = levstr(mid, midbegin, midroot - 1, lev);//左子树的层次序列
    rlv = levstr(mid, midroot + 1, midend, lev);//右子树的层次序列
    T->lchild = levmidCreatTree(mid, llv, midbegin, midroot - 1); // 左子树
    T->rchild = levmidCreatTree(mid, rlv, midroot + 1, midend);// 右子树
    return T;
}

string levstr(string mid, int midbegin, int midend, string lev)//寻找子树的层次遍历序列
{
    string result;
    int lv = 0, i;
    for (i = 0; i < (int)lev.length(); i++)
    {
        if (have(mid, midbegin, midend, lev[i]))
        {
            result[lv] = lev[i];
            lv++;
        }
    }
    return result;//子树的层次遍历序列
}

int have(string str, int begin, int end, char ch)//判断字符串str从begin到end之间有无ch字符
{
    int i;
    for (i = begin; i <= end; i++)
    {
        if (str[i] == ch)
        {
            return 1;
        }
    }
    return 0;
}
*///levstr()返回有错误

Bitree levmidCreatTree(Bitree &T,int l,string mid,string lev)
{//层次+中序建立二叉树
   int kidmid, i;
   T = NULL;
   for(i = 0; i < l; i++)//每一个层序元素依次插入二叉树
   {
        for(kidmid = 0; kidmid < l; kidmid++)
        if(mid[kidmid]==lev[i])//kidmid为层序元素在中序中的位置
          break;
        levmid(T, lev[i], kidmid, mid, l); // lev[i]为层序元素,T为根结点
   }
    return T;
}

void levmid(Bitree &T,char kid,int kidmid,string mid,int l)//kid为要插入点，kidmid为要插入点在中序中的位置
{
   if(T==NULL)
   {//从头结点开始，比较kid是被查找结点的左孩子还是右孩子，直到查找到NULL，每一个被查找点都是kid的祖先
        T = new BiNode;
        T->lchild = NULL;
        T->rchild = NULL;
        T->data = kid;//查找到NULL，将kid插入在此位置上
        return;//插入结束
   }
   int rootmid;//kid的祖先在中序中的位置
   for (rootmid= 0; kidmid < l; rootmid++)
   {
       if(mid[rootmid]==T->data)
        break;
   }
   if(kidmid<rootmid)//kid在中序中的位置在祖先左侧，为左孩子
       levmid(T->lchild, kid, kidmid, mid, l);
   else
       levmid(T->rchild, kid, kidmid, mid, l);
}

void dlroutput(Bitree T)//先序输出树
{
    if(T)
    {
        cout << T->data;//先序
        dlroutput(T->lchild);//左孩子
        dlroutput(T->rchild);//右孩子
    }
}

void ldroutput(Bitree T)//中序输出树
{
    if(T)
    {
        ldroutput(T->lchild);//左孩子
        cout << T->data;//中序
        ldroutput(T->rchild);//右孩子
    }
}

void lrdoutput(Bitree T)//后序输出树
{
    if(T)
    {
        lrdoutput(T->lchild);//左孩子
        lrdoutput(T->rchild);//右孩子
        cout << T->data;//后序
    }
}

void levoutput(Bitree T)//利用队列层次遍历输出树
{
    if(T==NULL)
        return;
    queue<Bitree> q;
    Bitree p;//end存当层最右边位置，nextend存下一层最右边位置
    q.push(T);//根入队
    while(!q.empty())
    {
        p = q.front();//p==队首
        q.pop();//队首出队
        cout << p->data;
        if(p->lchild!=NULL)//左孩子入队
        {
            q.push(p->lchild);
        }
        if(p->rchild!=NULL)//右孩子入队
        {
            q.push(p->rchild);
        }
    }
}

void output(Bitree T)
{
    cout << endl;
    cout << "二叉树的先序遍历序列:";
    dlroutput(T);
    cout << endl;
    cout << "二叉树的中序遍历序列:";
    ldroutput(T);
    cout << endl;
    cout << "二叉树的后序遍历序列:";
    lrdoutput(T);
    cout << endl;
    cout << "二叉树的层次遍历序列:";
    levoutput(T);
    cout << endl;
    cout << endl;
    cout << endl;
}

int main()
{
    Bitree T1,T2;
    int preend, midend, l;
    string pre, mid, lev;

    cinpremid(pre, mid);
    preend = pre.length() - 1;
    midend = mid.length() - 1;
    T1 = premidCreatTree(pre,0,preend,mid,0,midend);//先序+中序建立二叉树
    output(T1);

    cinlevmid(lev, mid);
    l = lev.length();
    T2 = levmidCreatTree(T2, l, mid, lev);//层次+中序建立二叉树
    output(T2);
    return 0;
}

/*
test1:
输入先序遍历序列:ABDC,中序遍历序列:BDAC
输入层次遍历序列:ABCD，中序遍历序列:BDAC

test2:
输入先序遍历序列:ABCDEFG，中序遍历序列:CDBAEFG
输入层次遍历序列:ABCDEF,中序遍历序列:DBEACF
*/